package binaryTree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 张取
 * @version 1.0
 * @date 2022/1/20 下午5:25
 * binaryTree
 */

public class PostorderTraversal {

    /** 递归后序遍历 */
    public LinkedList<Integer> rePostorderTrav(TreeNode root){
        LinkedList<Integer> nodes = new LinkedList<>();
        dfs(root, nodes);
        return nodes;
    }

    private void dfs(TreeNode root, LinkedList<Integer> nodes){
        if(root != null){
            dfs(root.left, nodes);
            dfs(root.right, nodes);
            nodes.offer(root.val);
        }
    }

    /** 迭代后序遍历 */
    public LinkedList<Integer> loopPostorderTrav(TreeNode root){
        LinkedList<Integer> nodes = new LinkedList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curNode = root;
        //存储上一次遍历的结点
        TreeNode prevNode = null;
        while(curNode != null || !stack.isEmpty()){
            while(curNode != null){
                //结点入栈，用于后面遍历
                stack.offerLast(curNode);
                //遍历左子树
                curNode = curNode.left;
            }
            //获取栈顶元素，但不出栈
            curNode = stack.peekLast();
            if(curNode.right != null && prevNode != curNode.right){
                //遍历右子树
                curNode = curNode.right;
            } else {
                curNode = stack.pollLast();
                //根
                nodes.offer(curNode.val);
                prevNode = curNode;
                curNode = null;
            }
        }
        return nodes;
    }
}
